Computer networking and communications may involve the transfer of millions of data packets simultaneously. In many environments, some network resources need to be reserved before starting to send data packets, to make data transfer more reliable. In such cases hundreds, thousands or more distributed entities compete to reserve the same resources by exchanging control packets for reservation. Generally, the entity that requests a particular resource is granted the use of that resource. However, because of the sheer volume of network traffic and the number of entities in a network, two or more entities may request the same resource at the same instant. The simultaneous conflicting requests for a resource is commonly known as a “collision,” and the process of determining which request will be accepted is known as a “collision resolution.”
In some environments collision resolution is performed locally by the network entity that has the requested resource. This resolution requires an exchange of control packets between the entities requesting the resource and the entity that has the requested resource. In other environments, collision resolution is performed directly by the entities requesting the resource, without involving the entity that has the requested resource. This form of collision resolution is known as a “distributed collision resolution,” since multiple entities participate in the collision resolution.
For example, a mesh network generally consists of a large number of nodes each connected to a small subset of the nodes on the network, i.e., not every node is directly connected to each other node. If a node wants to reserve a resource on the network, the node may simply “flood” the network by broadcasting its request to its immediate neighbors. In turn, each neighbor asks its own neighbors to forward the request to their neighbors. This process is repeated until all the nodes have been contacted. At the end of this flooding process, every node in the network learns that the initial node requests to reserve the resource, and the request is automatically accepted if no conflicting requests exist in the network. However, there are instances where more than one node may request to reserve the same resource at the same time, causing a collision. In these instances, the nodes need to make intelligent decisions concerning which request will be accepted.
The age of the request may be an important deciding factor in determining which request is accepted, i.e., the “winner,” and which request is not, i.e., the “loser,” in a distributed collision resolution. For example, if age is not used as a deciding factor, then a newer request for a resource can be a winner and an older request that was previously accepted can be a loser. But the resource may already be in use by the node that generated the older request, and this may cause the allocation of the resource to be transferred from one requester to the other prematurely. Such a case has to be avoided in many environments to avoid terminating file transfers in the middle, to avoid dropping voice conversations in the middle, and so on. Current methods of determining the winner and/or loser in a collision resolution where age is a deciding factor depend upon signaling or the use of synchronized clocks.
Signaling is a normal mechanism used to deal with resource requests; however, signaling requires a complex protocol to implement which consumes network resources and may cause processing delays. Another solution is to use actual clock time to set priorities, but this solution requires network-wide coordination of all the clocks. Not only is this solution expensive to implement, it may not be physically possible. Therefore, what is needed is a system and method for distributed collision resolution in a communication system where age is a deciding factor without using signaling or synchronized clocking.